// 结点类
class Node {
    //构造函数的输入：
    //d: 其它结点变量，或者是新结点的数据域
    //height: 该节点在画板中的高度
    //y: 该节点在画板中y轴坐标
    //parent: 父结点
    //loc: 该节点的类型，总共有三类："root", "left", "right" 分别表示根节点、左子结点、右子结点
    constructor(d, height, y, parent, loc) {
        if (d instanceof Node) {
            this.data = d.data;
            this.left = d.left;
            this.right = d.right;
            this.parent = d.parent;
            this.loc = d.loc;
            this.height = d.height;
            this.x = d.x;
            this.y = d.y;
            this.highlighted = d.highlighted;
        }
        else {
            this.data = d;
            this.left = null;
            this.right = null;
            this.parent = parent;
            this.loc = loc;
            this.height = height;
            this.x = canvasWidth / 2;
            this.y = y;
            this.highlighted = false;
        }
    }
}

// CLONE THE CURRENT TREE INCLUDING ITS CHILD AND THE CHILD OF ITS CHILD AND SO ON..
function treeClone(node) {
    if (node == null) return null;
    const neww = new Node(node);
    neww.left = treeClone(node.left);
    neww.right = treeClone(node.right);
    return neww;
}

// UNHIGHLIGHT ALL NODES
function unhighlightAll(node) {
    if (node !== null) {
      node.highlighted = false;
      unhighlightAll(node.left);
      unhighlightAll(node.right);
    }
  }
  
// GET CURRENT HEIGHT/LEVEL OF A NODE
function getHeight(node) {
    if (node == null) return 0;
    return node.height;
}
  

function updatePosition(node) {
    if (node != null) {
      if (node.loc === 'left') node.x = node.parent.x - ((2 ** (getHeight(node.right) + 1)) * 10);
      else if (node.loc === 'right') node.x = node.parent.x + ((2 ** (getHeight(node.left) + 1)) * 10);
      else if (node.loc === 'root') {
        node.x = canvasWidth / 2;
        node.y = 50;
      }
      if (node.parent != null) node.y = node.parent.y + 40;
      if (node.left != null) node.left.parent = node; // update parent information of current node
      if (node.right != null) node.right.parent = node; // update parent information of current node
      updatePosition(node.left);
      updatePosition(node.right);
    }
}

// 需要补全的函数：
// 在二叉排序树中执行插入操作
// 输入：
// node: 某级子树的根结点
// data: 待插入结点的数据域，新结点需要在该函数中自行创建
// posY: 新插入结点y轴坐标
// parent: 新插入结点的父结点
// loc: 新插入结点的类型，有用'root', 'left', 'right'三个字符串表示三种类型
// 
// 该函数在代码框架中被调用的方法为：
// tree = await pushElement(tree, value, 50, null, 'root');
// 其中 tree 表示二叉树的头结点，当树为空时，tree为 null
// value是输入栏中输入的数值 
// 50为默认的y轴坐标位置
// paren为 null, 因为在函数运行前尚不知道待插入结点的父结点是谁
// 新插入结点为叶子结点，所以默认类型为'root', 表示某级子树的根结点
//
// 其它部分请同学们自由发挥，只要保证该函数被调用之后，能正确返回二叉树的头指针即可
async function pushElement(node, data, posY, parent, loc) {
    // 代码中会用到的信息提示语句包括：
    // lastMsg = 'Found a null node. Inserted ' + data + '.';
    // lastMsg = data + ' < ' + curr.data + '. Looking at left subtree.';
    // lastMsg = data + ' >= ' + curr.data + '. Looking at right subtree.';
    // 以上提示语句的使用方法为：
    // lastMsg = 'Found a null node. Inserted ' + data + '.';
    // await sleep(delay);

    // 其它可能需要使用的函数：
    // let curr = new Node(data, 1, posY, parent, loc); // 创建新的结点
    // let curr = await pushElement(node, data, posY + 40, curr, 'left'); // 递归调用插入函数
    // curr.height = Math.max(getHeight(curr.left), getHeight(curr.right)) + 1; // 利用递归的方法计算当前结点应该有的高度

    let curr = node;
  
    if (curr != null) { // highlight current node in each recursion step
      curr.highlighted = true;
    }
  
    if (curr == null) { // if current node is null then place the new node there
      lastMsg = 'Found a null node. Inserted ' + data + '.';
      curr = new Node(data, 1, posY, parent, loc);
    }
    else if (data < curr.data) { // if new data < current node's data, then go to left subtree
      lastMsg = data + ' < ' + curr.data + '. Looking at left subtree.';
      await sleep(delay);
      curr.highlighted = false;
      curr.left = await pushElement(curr.left, data, posY + 40, curr, 'left');
    }
    else if (data >= curr.data) { // if new data >= current node's data, then go to right subtree
      lastMsg = data + ' >= ' + curr.data + '. Looking at right subtree.';
      await sleep(delay);
      curr.highlighted = false;
      curr.right = await pushElement(curr.right, data, posY + 40, curr, 'right');
    }
  
    curr.height = Math.max(getHeight(curr.left), getHeight(curr.right)) + 1; // update the heights of all nodes traversed by the pushElement() function
  
    return curr;
  }

// 需要补全的函数：
// 在二叉排序树中执行查找操作
// 输入：
// curr: 当前访问的结点
// key: 所要查找的数据域的数值
async function search(curr, key) {
    //代码中会用到的信息提示语句包括：
    // lastMsg = 'Searching for ' + key + ' : (Element not found)';
    // lastMsg = 'Searching for ' + key + ' : ' + key + ' < ' + curr.data + '. Looking at left subtree.';
    // lastMsg = 'Searching for ' + key + ' : ' + key + ' > ' + curr.data + '. Looking at right subtree.';
    // lastMsg = 'Searching for ' + key + ' : ' + key + ' == ' + curr.data + '. Element found!';
    // 以上提示语句的使用方法为：
    // lastMsg = 'Searching for ' + key + ' : (Element not found)';
    // await sleep(delay);

    // 可能会用到的函数：
    // unhighlightAll(tree); // 该函数会取消整个二叉树中所有被红框标记的节点
    // await search(curr, key); // 递归调用查找操作

    if (!curr) { // if current node is null then element does not exist in the tree
        lastMsg = 'Searching for ' + key + ' : (Element not found)';
        return 0;
    }
    unhighlightAll(tree);
    curr.highlighted = true;
    if (key < curr.data) { // if key < current node's data then look at the left subtree
        lastMsg = 'Searching for ' + key + ' : ' + key + ' < ' + curr.data + '. Looking at left subtree.';
        await sleep(delay);
        await search(curr.left, key);
    }
    else if (key > curr.data) { // if key > current node's data then look at the right subtree
        lastMsg = 'Searching for ' + key + ' : ' + key + ' > ' + curr.data + '. Looking at right subtree.';
        await sleep(delay);
        await search(curr.right, key);
    }
    else { // notify the main thread that an element is found and highlight that element
        lastMsg = 'Searching for ' + key + ' : ' + key + ' == ' + curr.data + '. Element found!';
        await sleep(delay);
    }
    return 0;
  }


// 需要补全的函数：
// 从头结点开始，在二叉排序树中执行前序遍历
// 输入：
// node: 某级子树的根结点
// 
// 该函数在代码框架中被调用的方法为：
// await getPreOrder(tree);
// 其中 tree 表示二叉树的头结点，当树为空时，tree为 null
async function getPreOrder(node) {
    // 在网页中打印遍历结果的方法：
    // lastMsg = 'Printing the value';
    // printOutput += node.data + ' ';
    // await sleep(delay);
    // 以上三条语句可以打印出 node.data 的数值

    // 可能会用到的函数：
    // unhighlightAll(tree); // 该函数会取消整个二叉树中所有被红框标记的节点
    // await getPreOrder(node); // 递归调用前序遍历操作

    if (node !== null) {
        unhighlightAll(tree);
        node.highlighted = true;
        lastMsg = 'Printing the value';
        printOutput += node.data + ' ';
        await sleep(delay);
        lastMsg = 'Going to left subtree';
        await sleep(delay);
    
        await getPreOrder(node.left);
    
        unhighlightAll(tree);
        node.highlighted = true;
        lastMsg = 'Going to right subtree';
        await sleep(delay);
    
        await getPreOrder(node.right);
    
        unhighlightAll(tree);
        node.highlighted = true;
        lastMsg = 'Going back up';
        await sleep(delay);
    }
    else {
        lastMsg += '... NULL';
        await sleep(delay);
    }
}
  
// 需要补全的函数：
// 从头结点开始，在二叉排序树中执行中序遍历
// 输入：
// node: 某级子树的根结点
// 
// 该函数在代码框架中被调用的方法为：
// await getInOrder(tree);
// 其中 tree 表示二叉树的头结点，当树为空时，tree为 null
async function getInOrder(node) {
    // 在网页中打印遍历结果的方法：
    // lastMsg = 'Printing the value';
    // printOutput += node.data + ' ';
    // await sleep(delay);
    // 以上三条语句可以打印出 node.data 的数值

    // 可能会用到的函数：
    // unhighlightAll(tree); // 该函数会取消整个二叉树中所有被红框标记的节点
    // await getInOrder(node); // 递归调用中序遍历操作

    if (node !== null) {
        unhighlightAll(tree);
        node.highlighted = true;
        lastMsg = 'Going to left subtree';
        await sleep(delay);
    
        await getInOrder(node.left);
    
        lastMsg = 'Printing the value';
        printOutput += node.data + ' ';
        unhighlightAll(tree);
        node.highlighted = true;
        await sleep(delay);
        lastMsg = 'Going to right subtree';
        await sleep(delay);
    
        await getInOrder(node.right);
    
        unhighlightAll(tree);
        node.highlighted = true;
        lastMsg = 'Going back up';
        await sleep(delay);
    }
    else {
        msg += '... NULL';
        await sleep(delay);
    }
}

// 需要补全的函数：
// 从头结点开始，在二叉排序树中执行后序遍历
// 输入：
// node: 某级子树的根结点
// 
// 该函数在代码框架中被调用的方法为：
// await getPostOrder(tree);
// 其中 tree 表示二叉树的头结点，当树为空时，tree为 null
async function getPostOrder(node) {
    // 在网页中打印遍历结果的方法：
    // lastMsg = 'Printing the value';
    // printOutput += node.data + ' ';
    // await sleep(delay);
    // 以上三条语句可以打印出 node.data 的数值

    // 可能会用到的函数：
    // unhighlightAll(tree); // 该函数会取消整个二叉树中所有被红框标记的节点
    // await getPostOrder(node); // 递归调用后序遍历操作

    if (node !== null) {
        unhighlightAll(tree);
        node.highlighted = true;
        lastMsg = 'Going to left subtree';
        await sleep(delay);
    
        await getPostOrder(node.left);
    
        unhighlightAll(tree);
        node.highlighted = true;
        lastMsg = 'Going to right subtree';
        await sleep(delay);
    
        await getPostOrder(node.right);
    
        lastMsg = 'Printing the value';
        printOutput += node.data + ' ';
        unhighlightAll(tree);
        node.highlighted = true;
        await sleep(delay);
        lastMsg = 'Going back up';
        await sleep(delay);
    }
    else {
        lastMsg += '... NULL';
        await sleep(delay);
    }
}